//
// 稀疏矩阵
//

#ifndef DATASTRUCTURECOURSE_GSPARSEMATRIX_H
#define DATASTRUCTURECOURSE_GSPARSEMATRIX_H


#include <vector>
#include <iostream>
#include <iomanip>

template<typename T>
class MatrixElement {
public:
    int row;
    int col;
    T value;

    MatrixElement() : row(0), col(0), value(0) {}

    MatrixElement(int r, int c, T v) : row(r), col(c), value(v) {}
};

template<typename T>
class [[maybe_unused]] GSparseMatrix {
private:
    int _rows;
    int _cols;
    std::vector<MatrixElement<T>> _matrix;

public:
    [[maybe_unused]] void add(int rowIndex, int columnIndex, T value) {
        _matrix.push_back(new MatrixElement<T>(rowIndex, columnIndex, value));
    }

    int include(int rowIndex, int columnIndex) {
        for (int i = 0; i < _matrix.size(); i++) {
            if (_matrix[i].row == rowIndex && _matrix[i].col == columnIndex) {
                return i;
            }
        }
        return -1;
    }

    [[maybe_unused]] void print() {
        for (int r = 0; r < _rows; r++) {
            for (int c = 0; c < _cols; c++) {
                int position = include(r, c);
                if (position > -1) {
                    std::cout << std::setw(5) << _matrix[position].value;
                } else {
                    std::cout << std::setw(5) << 0;
                }
            }
            std::cout << std::endl;
        }
    }

    [[maybe_unused]] void transpose() {
        // 转置后的矩阵每一行有几个
        std::vector<int> rowCounter(_cols, 0);
        for (auto element: _matrix) {
            rowCounter[element.col]++;
        }
        // 转置后的矩阵每一行元素的起始位置
        std::vector<int> startPosition(_cols, 0);
        startPosition[0] = 0;
        for (int i = 1; i < _cols; i++) {
            startPosition[i] = startPosition[i - 1] + rowCounter[i - 1];
        }
        std::vector<MatrixElement<T>> newMatrix(_matrix.size());
        for (int i = 0; i < _matrix.size(); i++) {
            newMatrix[startPosition[(_matrix[i].col)]].row = _matrix[i].col;
            newMatrix[startPosition[(_matrix[i].col)]].col = _matrix[i].row;
            newMatrix[startPosition[(_matrix[i].col)]].value = _matrix[i].value;
            startPosition[(_matrix[i].col)]++;
        }
        _matrix = newMatrix;
        std::swap(_rows, _cols);
    }

    [[maybe_unused]] GSparseMatrix(int rows, int columns) {
        _rows = rows;
        _cols = columns;
    }

};


#endif //DATASTRUCTURECOURSE_GSPARSEMATRIX_H
